GATE CSE 2014 SET-3
Q1.
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; }while (i <= j); if (listA[k] == x) return(k); else return -1; } Which one of the following statements about the function ProcessArray is CORRECT?Q2.
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n+m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is _______.Q3.
The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hit-ratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.Q6.
Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to theQ7.
Consider the following languages over the alphabet \sum =\{0,1,c\}: L_{1}=\{0^{n}|1^{n}|n\geq 0\} L_{2}=\{wcw^{r}|w\in \{0,1\}^{*}\} L_{3}=\{ww^{r}|w\in \{0,1\}^{*}\} Here w^{r} is the reverse of the string w. Which of these languages are deterministic Contextfree languages?Q8.
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): The average waiting time (in milliseconds) of the processes is _________.Q9.
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string isQ10.
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.